COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.rgp: NEWSEC RUNTIME SYSTEM
C00009 00003	.NEWSS TRAJECTORIES
C00021 00004	.NEWSS INTERPRETABLE CODE
C00031 00005	.NEWSS ALGORITHMS FOR USE OF GRAPH STRUCTURE
C00034 ENDMK
C⊗;
.rgp: NEWSEC RUNTIME SYSTEM

	This appendix discusses in greater detail some of the aspects
of the runtime system, which resides on the PDP11 as a set of programs
executing compiled code, operating devices in real time and receiving
sensory input.

.NEWSS THE RUNTIME SCHEDULER

	As mentioned earlier, in {secref run}, the runtime scheduling is
managed  through  a  combination  of  priority  level assignments  to
various types  of  processes  and  a time-slot  request  list.
The  PDP-11 hardware provides eight processor priority levels.  These
are assigned in the 'AL system as follows:
.BEGIN
.TABBREAK
.PREFACE 0
.NARROW 8,8
	7. AD (Analog-to-digital converter), joint servoing
	6. Clock, calendar
	5. <spare>
	4. condition monitors; Interrupt handlers for
	various condition-checking devices (eg finger pads).
	3. servo predictor
	2. <spare>
	1. Interpreters, scheduler for background stuff.
	0. Interpreters
.END

	 The 'AL system keeps a calendar of  things that must be done
in each time interval.  With time slot is associated:
.BEGIN
.TABBREAK
.PREFACE 0
.NARROW 8,8
	a. An AD command list which is to be started.
	b. A queue of procedure calls to make at various priority
levels.
.END

	Typically,  a servoing operation  will have two "phases", one
which  runs at level 7 as a response  to an AD-done interrupt and which is
responsible for emitting the new drive, and a somewhat lower priority
one  which requests  a  new time  slot from  the  calendar management
routine and  sets up  the correction  phase  for the  new slot.    As
previously indicated,  this first phase  is "scheduled" by  putting a
pointer to the appropriate AD command list into the "AD request" part
of a calendar  time slot.   The second phase  is scheduled merely  by
entering it onto the calendar queue  of things to be requested in the
same tick.  Joint servos are described more fully in the next section.

	If  a non-critical  process (eg,   a condition monitor)  needs a
"consistent" set of  AD measurements, it can  get them by setting  up
the appropriate AD  command list, finding a time  slot for taking the
measurements, and then placing a request that the computation that is
to use the set of  measurements be started up at the  time slot after
the one in which the measurements are made.  

	In  cases where a command  list is too long  to be finished in
one time slot, the  process requesting the measurements must  reserve
two (or more) contiguous slots.   This is done by placing the command
list id  in the first slot and a special flag value (perhaps -1) into
the remaining slots, so that  no other processes will try  to reserve
them.

.NEWSS TRAJECTORIES

	A trajectory for the hand is generated at compile time
under the assumption that the planning values for
the  initial point,  departure  point, via  points,
arrival  point and  final  position  are accurate.

	If at  run time it is found that some or all of these planned
positions have  moved slightly  it  becomes necessary  to modify  the
planned  trajectory to  pass through  the actual  positions.   If the
actual  positions  are  only  slightly  different  from  the  planned
positions then the  trajectory is still  almost optimal, that  is, it
still has most of  the properties with which it was designed.  If the
deviation from the planned  values to the  actual are great then  the
trajectory is  no longer  optimal.   To plan  a new  trajectory would
again optimize the move, but only if the time to compute is less than
the time saved  is it worth recomputing.  At present this is  not the
case,  so no  recalculation of  trajectories is  done.   Instead, the
following trajectory modification step is performed:

	Before the move is executed, it is prepared by computing  the
discrepancies between actual locations and  planned locations.  Fifth
degree  interpolating   polynomials  (with  zero  initial  and  final
velocity and acceleration) are computed to be added into  the planned
polynomials to bring  the planned trajectory into  line with reality.
The  joint angles associated with  a frame are  stored along with its
matrix, so this often  does not involve much calculation,  unless the
frame has been changed  since these calculations were done last. Also
at this time the joint  inertias and gravity loadings are  calculated
and stored in the value cell of relevant frames.

.NEWSS JOINT SERVOING

	Any coordinated  motion of the  arm can  be expressed as  six
time dependent motions, one for each joint; the coordinated motion is
parameterized in terms of time.  The problem of servoing the arm,  or
arms, is  thus reduced to  a problem of  servoing a number  of joints
with respect to time.

	A joint  servo has two  parts: a drive  part and  a predictor
part. As mentioned  before, the drive part is run at priority level 7.
When  it  finishes,  the  servo  enters  priority  level  3  for  the
predictor. First, the  predictor reserves a time for the  next run of
this  servo. The  delay is  chosen based  on considerations  of joint
response time, joint velocity, and availability of time slots.

	Now the  predictor evaluates  the motion  polynomial for  the
time which it has reserved.  This evaluation may take into account an
interpolating   polynomial    used   for    last-minute    trajectory
modification, as well  as any offset  that might be necessary  due to
modifications being made during the motion itself. These calculations
give  the  predicted   set  point.     The  predicted  velocity   and
acceleration are  obtained by  difference techniques based  on recent
set  point values.  The  joint inertia and  gravity force loading are
interpolated.  The  gravity loading  is added to  the product of  the
predicted  acceleration and the  joint inertia  to yield  a predicted
drive.

	If this joint has multiple wipers then the appropriate  wiper
to read the joint position is determined.  Then the joint calibration
is  applied to  the  set point  to yield  the  expected potentiometer
reading for the joint  at the reserved  time. The servo gains,  which
are dependent on joint inertia,  are next calculated, and finally the
servo equation is set up in terms of observed position and velocity.
The  form of the  servo equation is dependent  on whether the
joint  is being  run  with  position, velocity,  or  force  servoing.
Having  done all  this  predictive work,  the  joint servo  dismisses
control.

	When the reserved time  occurs, the drive  part of the  servo
runs in priority  level 7. The  drive part measures the  position and
velocity,   evaluates the  servo equation prepared  by the predictor,
applies friction compensation  and drives the joint.  This is a  very
fast  computation and  minimizes  any delay  between observation  and
action.  The   predictor  is  then  run  again  for  the  next  servo
scheduling, as described above.

	Upon completion of the motion, or if some error should occur,
or  if some other  process requests  that the joint  stop, completion
codes are set for the joint, and then the servo terminates.

	The advantage of this servo scheme is that it allows flexible
scheduling: each joint can  run at its own required  repetition rate.
As  the joint  knows  when it  will  be run  next it  is  possible to
pre-compute most of the drive and thus reduce the servo delay.

	Each servo routine has a control block which includes a status
register. In the
case  of a  joint servo  the status  register contains  the following
bits:
.UNFILL;
	RUN		joint is running or about to be run
	FIRST		first time through loop for this motion.
	FINAL		in final state, nulling errors
	STOP		stop this joint, or joint is stopped
	EXFORCE		joint stopped due to excessive force.
	ADERR		a/d error
	NONEX		joint is down or does not exist
	STERR		servo was not run on schedule
	SERVO		position servo
	VELS		velocity servo
	FORCE		exert force
	WOB		perturb this joint while running
	NUL		null errors at end and stop
.REFILL

	When the servo is started up for the  first time, it is given
certain information,  including which  joint it should
servo, what  the properties  of that  joint are,  what polynomial  to
follow, the predicted gravity torque and inertia loadings.

This system allows us to move the arm and to carry loads; it is
possible to exert forces along various free directions. The system as
it is described here is incapable of interacting with live loads,
springs, partially submerged objects and other objects with complex
reactions to forces.

.NEWSS INTERPRETABLE CODE
.TURN ON "←";

The runtime interpreters act by interpreting a special kind of
code generated by the compiler.  The %4pseudo operations%* available
include stack manipulation, flow-of-control primitives, device
control, and arithmetic.  Arithmetic routines always take their
arguments from the stack, which contains pointers to value cells.
Variables are accessed through %4environments%*: an environment
points to all the variables local to a particular block level
and also to the environment in force at the next global level.
  When one interpreter sprouts several
subsidiary interpreters (to implement a simultaneous block, for
example), each new interpreter gets a new environment which points
to the old one; thus they all share global information.

Arguments are stored immediately after those pseudo-instructions
which need them.  

Here is a list of the pseudo-operations currently available:
.SKIP SPREAD
←STACK OPERATORS
.BEGIN INDENT 0,16
.PREFACE 0
gtval  <arg>	\The argument has two fields: lexical level and offset.
		Together, these determine a variable.  The value of that
		variable is extracted from the graph structure and a
		pointer to it is placed on the stack.

chnge  <arg>	\The argument again determines a variable.  The value
		currently pointed to by the top of the stack is stored into
		that variable, and all necessary updating of the
		graph structure is performed.

pop		\pops the stack.

copy <num>	\finds the <num>'th element down in the stack (this will be
		a pointer to some value cell) and copy it to the top.

copys		\make a new scalar value cell; initialize it to the same
		value as the cell currently pointed to by the top of the
		stack, and push it.

copyv		\make a new vector value cell; initialize it to the same
		value as the cell currently pointed to by the top of the
		stack, and push it.

copyr		\make a new rot value cell; initialize it to the same
		value as the cell currently pointed to by the top of the
		stack, and push it.

copyf		\make a new frame value cell; initialize it to the same
		value as the cell currently pointed to by the top of the
		stack, and push it.

copyp		\make a new plane value cell; initialize it to the same
		value as the cell currently pointed to by the top of the
		stack, and push it.

copyt		\make a new trans value cell; initialize it to the same
		value as the cell currently pointed to by the top of the
		stack, and push it.

flush		\clears the stack.

.END


←ARITHMETIC

	Arithmetic routines are supplied for all the operations described
in {sssref arith}.  The stack contains pointers to the value cells needed
as arguments.  After the operation is completed, all argument pointers 
are popped from the stack, and a pointer to the result value cell is pushed
onto the stack.

←FLOW OF CONTROL
.BEGIN INDENT 0,16
.PREFACE 0

proc		\Procedure call; takes as arguments the destination
		address, the argument list.  All value parameters 
		should first have been copied into temps.

return		\Procedure return

sprout		\Start up a new interpreter.  The single argument tells
		where its code is to be found.

enable <arg>	\start up an on-monitor with location of status word <arg>.

disable <arg>	\the on-monitor with location of status word <arg> is disabled.

wait		\wait until all descendant (non on-monitor) processes are dead.
		  Then kill descendant move on-monitors and continue.

terminate	\terminate this process.  Should first call "wait".

jump <arg>	\unconditional jump to indicated location in interpreter code.

jumpp <arg>	\conditional jump on positive element at top of stack.

jumpz <arg>	\conditional jump on zero element at top of stack.

nop		\no-op.
.END

←ARM AND DEVICE CONTROL
.BEGIN INDENT 0,16
.PREFACE 0

prepmove <arg>	\<arg> points to the move vector.  Trajectory modification
		  happens now.

startmove	\sprouts joint servos and move-monitors

search <arg>	\<arg> points to the search vector.

stop <arg>	\<arg> encoding of what devices must be stopped.
.END

←INPUT AND OUTPUT

	Some sort of I/O will be implemented, most likely including string
output to the supervisor, error message output, and input (from supervisor
or from coresident routines) of value cells.

←DEBUGGING AIDS
.BEGIN INDENT 0,16
.PREFACE 0

source <arg>	\notes that <arg> is where the interpreter is now in
		  source code.

tellsource	\output current source location to the 10.

step		\begins step mode, which does one interpretation at a time,
		  requires message to continue.

offstep		\turns off step mode; normal speed is resumed.
.END
.TURN OFF "←";

.NEWSS ALGORITHMS FOR USE OF GRAPH STRUCTURE

These are the algorithms (written in an Algol-like fashion) used to
find values for variables in the graph structure and to change those
values. 

.UNFILL
PROCEDURE invalidate (POINTER(NODE) n);
	IF invmark(n)=0 THEN
		BEGIN  COMMENT:  This cell currently marked valid;
		POINTER p;
		invmark(n)α← -1;
		p α← dependents(n);
		WHILE p%7≠%*NULL DO
			BEGIN  COMMENT: Mark all dependents as invalid;
			invalidate(p);
			p α← link(p)
			END
		END;

.REFILL

.UNFILL
PROCEDURE change (POINTER(NODE) n; POINTER(VALUE) vnew);
	BEGIN
	COMMENT:  This procedure is called in order to explicitly assign
		a new value, vnew, to node n;
	POINTER(VALUE) vold;
	invalidate(n);
	vold α← value(n);
	value(n)α←vnew;
	p α← changer(n);
	WHILE p%7≠%*NULL DO
		BEGIN  COMMENT:  Handle all changers;
		APPLY(code(p),vold,vnew);
		p α← link(p);
		END;
	invmark(n) α← 0;
	END;

.REFILL

.UNFILL
POINTER(VALUE) PROCEDURE getvalue (POINTER(NODE) n);
	BEGIN
	IF invmark(n)%7≠%*0 THEN evalnode(n, time α← time+1);
	RETURN(value(n));
	END;

.REFILL

.UNFILL
PROCEDURE evalnode (POINTER(NODE) n, INTEGER t);
	BEGIN  COMMENT:  Put a good value in the value cell of n.
		t is used to break cycles;
	IF invmark(n)=0 ∨ invmark(n)=t THEN RETURN;
	invmark(n) α← t;
	p α← calculator(n);
	WHILE p %7≠%* NULL DO
		BEGIN "cloop"
		POINTER(node) d;
		d α← needed(p);
		WHILE d %7≠%* NULL DO
			BEGIN
			evalnode(node(d),t);
			IF invmark(dep(d))%7≠%*0 THEN
				BEGIN
				p α← next(p);
				CONTINUE "cloop";
				END;
			d α← next(d);
			END;
		value(n)α←APPLY(code(p), args(p));
		invmark(n)α←0;
		RETURN;
		END;
	END;
.REFILL